package xio.leetcode.java;

import java.util.Arrays;

/**
 * 684. Redundant Connection (Medium)
 * 在本问题中, 树指的是一个连通且无环的无向图。
 * <p>
 * 输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
 * <p>
 * 结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
 * <p>
 * 返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。
 * <p>
 * 示例 1：
 * <p>
 * 输入: [[1,2], [1,3], [2,3]]
 * 输出: [2,3]
 * 解释: 给定的无向图为:
 *    1
 *  /  \
 * 2 - 3
 * 思路：动态连通性，上并查集!
 */
public class LC684_RedundantConnection {
    public int[] findRedundantConnection(int[][] edges) {
        UnionFind uf = new UnionFind(edges.length+1);
        for (int[] e : edges) {
            if (uf.connected(e[0],e[1])){
                return e;
            }
            uf.union(e[0],e[1]);
        }
        return null;
    }

    /** 并查集 */
    class UnionFind {
        private int[] id;  //节点分量标识
        private int[] nodeNum; //分量的节点数量

        public UnionFind(int N) {
            id = new int[N];
            nodeNum = new int[N];
            for (int i = 0; i < N; i++) id[i] = i;
            for (int i = 0; i < N; i++) nodeNum[i] = 1;
        }

        //返回节点的分量标识
        public int find(int value) {
            while (value != id[value]) {
                id[value] = id[id[value]];  //路径压缩
                value = id[value];
            }
            return value;
        }

        //判断节点是否连通
        public boolean connected(int value1, int value2) {
            int id1 = find(value1);
            int id2 = find(value2);
            return id1 == id2;
        }

        //分量归并
        public void union(int value1, int value2) {
            int root1 = find(value1);
            int root2 = find(value2);
            int nodeNum1 = nodeNum[root1];
            int nodeNum2 = nodeNum[root2];
            if (root1 == root2) {
                return;
            }
             if (nodeNum1 < nodeNum2) {
                id[root1] = root2;
                nodeNum[root2] = nodeNum1 + nodeNum2;
            } else {
                id[root2] = root1;
                nodeNum[root1] = nodeNum1 + nodeNum2;
            }
        }
    }

    public static void main(String[] args) {
        LC684_RedundantConnection rc = new LC684_RedundantConnection();
        int[] e = rc.findRedundantConnection(new int[][]{{1, 2}, {1, 3}, {2, 3}});
        System.out.println(Arrays.toString(e));
    }

}
